package nowCoder;

import java.util.ArrayList;
import java.util.Arrays;

public class CombineandSort {
	public void permutate(char[] chars, int start, ArrayList<String> rst){
		if(start==chars.length-1){
			String rstString = String.copyValueOf(chars);
			rst.add(rstString);
			return;
		}
		
		char flag = chars[start];
		for(int i=start;i<chars.length;i++){
			if(i>start && chars[i]==chars[start])
				continue;
			chars[start] = chars[i];
			chars[i]= flag;
			permutate(chars, start+1, rst);
			chars[i] = chars[start];
			chars[start] = flag;
		}
	}
	public ArrayList<String> Permutation(String str) {
		if(null == str || str.length()==0)
			return new ArrayList<String>(); 
		char[] chars = str.toCharArray();
		ArrayList<String> rst = new ArrayList<String>();
		
		
		permutate(chars, 0, rst);
		String[] rstStrings = new String[rst.size()];
		rst.toArray(rstStrings);
		Arrays.sort(rstStrings);
		rst.clear();
		for(String s:rstStrings)
			rst.add(s);
		return rst;
	}
	
	public static void main(String[] args){
		CombineandSort combineandSort = new CombineandSort();
		String str = "Abc";
		ArrayList<String> rst = combineandSort.Permutation(str);
		System.out.println(rst);
		
	}
}
